//#define  _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <map>
//#include <unordered_map>
//#include <vector>
//#include <algorithm>
//#include <ctime>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> v(n + 1);
//	for (int i = 1; i <= n; i++)
//		cin >> v[i];
//
//	map<int, vector<int>, greater<int>> mp;
//	int tmp1, tmp2;
//	for (int i = 0; i < n - 1; i++)
//	{
//		cin >> tmp1 >> tmp2;
//		mp[tmp1].push_back(tmp2);
//	}
//	cout << 1000;
//	return 0;
//
//}
//
///*map<int, vector<int>> mp2;
//for (auto it = mp.begin(); it != mp.end(); it++)
//{
//	sort(it->second.begin(), it->second.end());
//	int sum = 0;
//	for (int i = 0; i < it->second.size(); i++)
//		sum += v[it->second[i]];
//	if (sum < v[it->first]) mp2[it->first].push_back(sum);
//	for (int i = it->second.size() - 1; i >= 0; i--)
//	{
//		sum -= v[it->second[i]];
//		if (sum < v[it->first]) mp2[it->first].push_back(sum);
//	}
//}*/
//
//
///*
//9
//9 7 3 7 1 6 2 2 7
//1 2
//1 3
//2 4
//2 5
//2 6
//6 7
//6 8
//6 9
//*/